package com.company.algo.graph;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/find-eventual-safe-states/
 */
public class find_eventual_safe_states {
    //图的判环
    //1.通过visited记录以访问过的元素，如果当前待访问元素已在visited中，则说明有环
    //2.dfs每个起点(start)，若visited[start]==true，则返回false
    boolean[] visited;
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> res = new ArrayList<>();
        visited = new boolean[graph.length];
        for (int i = 0; i < graph.length; i++) {
            if (dfs(i,graph)) res.add(i);
        }
        return res;
    }

    boolean dfs(int start, int[][]graph){
        if (visited[start]) return false;
        visited[start] = true;
        for(int neighbor:graph[start]){
            if (!dfs(neighbor,graph)) return false;
        }
        visited[start] = false;
        return true;
    }

    public static void main(String[] args) {
        int[][] graph = new int[5][];
        graph[0] = new int[]{};
        graph[1] = new int[]{0,2,3,4};
        graph[2] = new int[]{3};
        graph[3] = new int[]{4};
        graph[4] = new int[]{};
//        graph[5] = new int[]{};
//        graph[6] = new int[]{};
        find_eventual_safe_states Main = new find_eventual_safe_states();
        System.out.println(Main.eventualSafeNodes(graph));
    }
}
